use avl_tree::avl_tree::{AVLTree, AVLTreeNodeSide};
use std::cmp::Ordering;

fn int_compare(left: &i32, right: &i32) -> Ordering {
    left.cmp(right)
}

#[test]
fn test_avl_tree_new() {
    let tree: AVLTree<i32, i32> = AVLTree::new(int_compare);
    assert!(tree.root_node.is_none());
    assert_eq!(tree.num_entries(), 0);
}

#[test]
fn test_avl_tree_insert_lookup() {
    let mut tree = AVLTree::new(int_compare);
    let num_test_values = 1000;
    let mut test_array = vec![0; num_test_values];

    for i in 0..num_test_values {
        test_array[i] = i as i32;
        tree.insert(test_array[i], test_array[i]);
        assert_eq!(tree.num_entries(), i + 1);
    }

    assert!(tree.root_node.is_some());

    for i in 0..num_test_values {
        let node = tree.lookup_node(&(i as i32));
        assert!(node.is_some());
        let node = node.unwrap();
        let node_borrow = node.borrow();
        assert_eq!(*node_borrow.key(), i as i32);
        assert_eq!(*node_borrow.value(), i as i32);
    }

    let invalid_key = num_test_values as i32 + 100;
    assert!(tree.lookup_node(&invalid_key).is_none());
}

#[test]
fn test_avl_tree_child() {
    let mut tree = AVLTree::new(int_compare);
    let values = [1, 2, 3];

    for &value in &values {
        tree.insert(value, value);
    }

    let root = tree.root_node.as_ref().unwrap();
    let root_borrow = root.borrow();
    assert_eq!(*root_borrow.value(), 2);

    let left = root_borrow.child(AVLTreeNodeSide::Left);
    assert!(left.is_some());
    let left = left.unwrap();
    let left_borrow = left.borrow();
    assert_eq!(*left_borrow.value(), 1);

    let right = root_borrow.child(AVLTreeNodeSide::Right);
    assert!(right.is_some());
    let right = right.unwrap();
    let right_borrow = right.borrow();
    assert_eq!(*right_borrow.value(), 3);

    assert!(root_borrow.child(AVLTreeNodeSide::Left).is_some());
    assert!(root_borrow.child(AVLTreeNodeSide::Right).is_some());
}

#[test]
fn test_avl_tree_free() {
    let mut tree = AVLTree::new(int_compare);
    tree.insert(1, 1);
    tree.insert(2, 2);
    tree.insert(3, 3);
    assert_eq!(tree.num_entries(), 3);
    drop(tree);
}

#[test]
fn test_avl_tree_lookup() {
    let mut tree = AVLTree::new(int_compare);
    let num_test_values = 1000;
    let mut test_array = vec![0; num_test_values];

    for i in 0..num_test_values {
        test_array[i] = i as i32;
        tree.insert(test_array[i], test_array[i]);
    }

    for i in 0..num_test_values {
        let node = tree.lookup_node(&(i as i32));
        assert!(node.is_some());
        let node = node.unwrap();
        let node_borrow = node.borrow();
        assert_eq!(*node_borrow.value(), i as i32);
    }

    let invalid_key = -1;
    assert!(tree.lookup_node(&invalid_key).is_none());
    for i in 0..num_test_values {
        test_array[i] = i as i32;
        tree.insert(test_array[i], test_array[i]);
    }

    let mut expected_entries = num_test_values;
    let mut expected_entries = num_test_values;
    
    let mut tree = AVLTree::new(int_compare);
    let entries = [89, 23, 42, 4, 16, 15, 8, 99, 50, 30];
    let sorted = [4, 8, 15, 16, 23, 30, 42, 50, 89, 99];

    for &entry in &entries {
        tree.insert(entry, entry);
    }

    let array = tree.to_array();
    for i in 0..sorted.len() {
        assert_eq!(array[i], sorted[i]);
    }
}

#[test]
fn test_avl_tree_to_array() {
    let mut tree = AVLTree::new(int_compare);
    let entries = [89, 23, 42, 4, 16, 15, 8, 99, 50, 30];
    let sorted = [4, 8, 15, 16, 23, 30, 42, 50, 89, 99];

    for &entry in &entries {
        tree.insert(entry, entry);
    }

    let array = tree.to_array();
    for i in 0..sorted.len() {
        assert_eq!(array[i], sorted[i]);
    }
}